package leetcode.code1621;

public class Solution {

	int mod = (int) 1e9 + 7;

	public int numberOfSets(int n, int k) {
		long[][] dp = new long[k + 1][n + 1];
		long[][] sums = new long[k + 1][n + 1];
		for (int j = 1; j <= n; j++) {
			dp[1][j] = dp[1][j - 1] + j - 1;
			sums[1][j] = sums[1][j - 1] + dp[1][j];
			dp[1][j] %= mod;
			sums[1][j] %= mod;
		}
		for (int i = 2; i <= k; i++) {
			for (int j = 1; j <= n; j++) {
				dp[i][j] = dp[i][j - 1] + sums[i - 1][j - 1];
				sums[i][j] = sums[i][j - 1] + dp[i][j];
				dp[i][j] %= mod;
				sums[i][j] %= mod;
			}
		}
		return (int) dp[k][n];
	}
}
